package leetcode;

/**
 * Created by Ghost on 2014/11/26 0026.
 */
public class Add_Binary {
    public String addBinary(String a, String b) {
        int aa=0,bb=0;
        for(;aa<a.length() && a.charAt(aa)=='0';aa++);
        for(;bb<b.length() && b.charAt(bb)=='0';bb++);

        if(aa==a.length() && bb!=b.length())
            return b.substring(bb);
        if(bb==b.length() && aa!=a.length())
            return a.substring(aa);
        if(aa==a.length() && bb==b.length())
            return ""+0;
        char[] A;
        char[] B;

        StringBuilder sba = new StringBuilder(a.substring(aa));
        a = sba.reverse().toString();
        StringBuilder sbb = new StringBuilder(b.substring(bb));
        b = sbb.reverse().toString();

        if (a.length() > b.length()) {
            A = a.toCharArray();
            B = b.toCharArray();
        } else {
            A = b.toCharArray();
            B = a.toCharArray();
        }
        int i = 0;
        int c = 0;
        while (i < B.length) {
            int tmp = (A[i] - '0' + B[i] - '0' + c) % 2;
            c = (A[i] - '0' + B[i] - '0' + c) / 2;
            A[i] = (char) ('0' + tmp);
            i++;
        }
        while (i < A.length) {
            int tmp = (A[i] - '0' + c) % 2;
            c = (A[i] - '0' + c) / 2;
            A[i] = (char) ('0' + tmp);
            i++;
        }

        if(c==1){
            StringBuilder sb = new StringBuilder(String.valueOf(A)).append('1').reverse();
            return sb.toString();
        }
        else
            return new StringBuilder(String.valueOf(A)).reverse().toString();
    }
    public static void main(String[] args){
        Add_Binary add_binary = new Add_Binary();
        System.out.println(add_binary.addBinary("01","01"));
    }
}
